package offer;

import java.util.List;

public class offerII_0063 {
    public String replaceWords(List<String> dictionary, String sentence) {
        preword head=new preword();
        head.build(dictionary);
        String[] list=sentence.split(" ");
        int len=list.length;
        for(int i=0;i<len;++i){
            String s=head.search(list[i]);
            if(!"".equals(s)){
                list[i]=s;
            }
        }
        String result="";
        for(int i=0;i<len;++i){
            if(i!=0){
                result+=" ";
            }
            result+=list[i];
        }
        return result;
    }

    class preword {
        preword[] list;
        public boolean empty;
        public boolean end;
        public preword(){
            empty=true;
            end=false;
            list=new preword[26];
        }
        public String search(String s){
            int len=s.length();
            String result="";
            preword tmp=this;
            for(int i=0;i<len;++i){
                tmp=tmp.list[s.charAt(i)-'a'];
                if(tmp==null) return "";
                if(tmp.empty==true) return "";
                result+=s.charAt(i);
                if(tmp.end==true) return result;
            }
            return "";
        }
        public void build(List<String> dictionary){
            int len=dictionary.size();
            for(int i=0;i<len;++i){
                preword tmp=this;
                String s=dictionary.get(i);
                int strlen=s.length();
                for(int j=0;j<strlen;++j){
                    if(tmp.list[s.charAt(j)-'a']==null) tmp.list[s.charAt(j)-'a']=new preword();
                    tmp=tmp.list[s.charAt(j)-'a'];
                    tmp.empty=false;
                    if(j==strlen-1) tmp.end=true;
                }
            }
        }
    }
}
